package q491_findSubsequences;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {

    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> bin = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        dfs(nums, 0);
        return res;
    }

    void dfs(int[] nums, int start){
        if (bin.size() > 1){
            res.add(new ArrayList<>(bin));
        }

        if (start >= nums.length){
            return;
        }

        /*
          这里涉及到同层元素去重
          我们以 4 6 7 7 为例
          当我们前两次dfs分别会加入 4 6 两个元素
          然后到7时，如果没有进行去重那么在第一个7这一层，树枝就会发展到收录 4 6 7 然后是 4 6 7 7
          然后这一层的循环又会指向第二个7 也就会产生第二个4 6 7 所以我们要在同层内进行去重，避免有重复的元素
          此时就需要一个set
          关键在于set的位置定义在什么地方：
          如果定义在dfs外,那么就会导致在结果中的任何一项都不能有重复元素
          例如4 6 7 7 就不存在
          并且仍然有重复的情况 因为我们的原则是在dfs后要消除set添加的元素，所以对于后面的树枝没有作用

          所以这个set是定义在dfs方法内部的，很容易看出它的作用就是在这一层的 ***for循环内部***
          如果这一层for循环有一个一样的数，就不会执行
         */
        Set<Integer> set = new HashSet<>();
        for (int i = start; i < nums.length; i++){
            if ((!set.contains(nums[i]))&&(bin.size() == 0 || nums[i] >= bin.get(bin.size() - 1))){
                set.add(nums[i]);
                bin.add(nums[i]);
                dfs(nums, i + 1);
                bin.remove(bin.size() - 1);
            }
        }
    }
}
